Quasiperiodicity and string covering
Identifieur interne : 00C423 ( Main/Exploration ); précédent : 00C422; suivant : 00C424Quasiperiodicity and string covering
Auteurs : Costas S. Iliopoulos [Royaume-Uni, Australie] ; Laurent Mouchard [Royaume-Uni, France]Source :
- Theoretical Computer Science [ 0304-3975 ] ; 1999.
Descripteurs français
- Pascal (Inist)
English descriptors
- KwdEn :
- Abaaba, Algorithm, Appropriate factor, Computer science, Concatenation, Easy seed, Easy seeds, Ehrenfeucht algorithm, Elsevier science, Failure function, Formal language, Formal language theory, Hard seed, Hard seeds, Iliopoulos, Language theory, Lecture notes, Local period, Longest span, Main steps, Maximal quasiperiodic factors, Mouchardl, Optimal algorithm, Parallel string, Periodic words, Periodicity, Proper factor, Quasi periodic variation, Quasiperiodic, Quasiperiodic factor, Quasiperiodicity, Quasiperiodicity problem, Regularity, Right extension, String matching, Superposition, Wide area.
- Teeft :
- Abaaba, Algorithm, Appropriate factor, Computer science, Concatenation, Easy seed, Easy seeds, Ehrenfeucht algorithm, Elsevier science, Failure function, Formal language theory, Hard seed, Hard seeds, Iliopoulos, Lecture notes, Local period, Longest span, Main steps, Maximal quasiperiodic factors, Mouchardl, Optimal algorithm, Parallel string, Periodic words, Periodicity, Proper factor, Quasiperiodic, Quasiperiodic factor, Quasiperiodicity, Quasiperiodicity problem, Regularity, Right extension, Superposition, Wide area.
Abstract
Abstract: In this paper, we study word regularities and in particular extensions of the notion of the word period: quasiperiodicity, covers and seeds. We present overviews of algorithms for computing the quasiperiodicity, the covers and the seeds of a given word. We also present an overview of an algorithm that finds maximal word factors with the above regularities. Finally, we show how Fine and Wilf's Theorem fails if we try to extend it directly to quasiperiodicity, as well as a new property on concatenation of periodic words.
Url:
DOI: 10.1016/S0304-3975(98)00260-6
Affiliations:
Links toward previous steps (curation, corpus...)
- to stream Istex, to step Corpus: 000312
- to stream Istex, to step Curation: 000312
- to stream Istex, to step Checkpoint: 002084
- to stream Main, to step Merge: 00D396
- to stream PascalFrancis, to step Corpus: 006283
- to stream PascalFrancis, to step Curation: 006D71
- to stream PascalFrancis, to step Checkpoint: 005F26
- to stream Main, to step Merge: 00D639
- to stream Main, to step Curation: 00C423
Le document en format XML
<record><TEI wicri:istexFullTextTei="biblStruct"><teiHeader><fileDesc><titleStmt><title>Quasiperiodicity and string covering</title><author><name sortKey="Iliopoulos, Costas S" sort="Iliopoulos, Costas S" uniqKey="Iliopoulos C" first="Costas S." last="Iliopoulos">Costas S. Iliopoulos</name></author><author><name sortKey="Mouchard, Laurent" sort="Mouchard, Laurent" uniqKey="Mouchard L" first="Laurent" last="Mouchard">Laurent Mouchard</name></author></titleStmt><publicationStmt><idno type="wicri:source">ISTEX</idno><idno type="RBID">ISTEX:10737BF78BD626F99E6C0CB224A3C20D46D86E87</idno><date when="1999" year="1999">1999</date><idno type="doi">10.1016/S0304-3975(98)00260-6</idno><idno type="url">https://api.istex.fr/document/10737BF78BD626F99E6C0CB224A3C20D46D86E87/fulltext/pdf</idno><idno type="wicri:Area/Istex/Corpus">000312</idno><idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Corpus" wicri:corpus="ISTEX">000312</idno><idno type="wicri:Area/Istex/Curation">000312</idno><idno type="wicri:Area/Istex/Checkpoint">002084</idno><idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Checkpoint">002084</idno><idno type="wicri:doubleKey">0304-3975:1999:Iliopoulos C:quasiperiodicity:and:string</idno><idno type="wicri:Area/Main/Merge">00D396</idno><idno type="wicri:source">INIST</idno><idno type="RBID">Pascal:99-0409678</idno><idno type="wicri:Area/PascalFrancis/Corpus">006283</idno><idno type="wicri:Area/PascalFrancis/Curation">006D71</idno><idno type="wicri:Area/PascalFrancis/Checkpoint">005F26</idno><idno type="wicri:explorRef" wicri:stream="PascalFrancis" wicri:step="Checkpoint">005F26</idno><idno type="wicri:doubleKey">0304-3975:1999:Iliopoulos C:quasiperiodicity:and:string</idno><idno type="wicri:Area/Main/Merge">00D639</idno><idno type="wicri:Area/Main/Curation">00C423</idno><idno type="wicri:Area/Main/Exploration">00C423</idno></publicationStmt><sourceDesc><biblStruct><analytic><title level="a">Quasiperiodicity and string covering</title><author><name sortKey="Iliopoulos, Costas S" sort="Iliopoulos, Costas S" uniqKey="Iliopoulos C" first="Costas S." last="Iliopoulos">Costas S. Iliopoulos</name><affiliation wicri:level="1"><country xml:lang="fr">Royaume-Uni</country><wicri:regionArea>Deptartment of Computer Science, King's College London, Strand, London, WC2R 2LS</wicri:regionArea><wicri:noRegion>WC2R 2LS</wicri:noRegion></affiliation><affiliation wicri:level="1"><country xml:lang="fr">Australie</country><wicri:regionArea>School of Computing, Curtin University of Technology, GPO Box U1987, Perth 6845</wicri:regionArea><wicri:noRegion>Perth 6845</wicri:noRegion></affiliation></author><author><name sortKey="Mouchard, Laurent" sort="Mouchard, Laurent" uniqKey="Mouchard L" first="Laurent" last="Mouchard">Laurent Mouchard</name><affiliation></affiliation><affiliation wicri:level="1"><country xml:lang="fr">Royaume-Uni</country><wicri:regionArea>Deptartment of Computer Science, King's College London, Strand, London, WC2R 2LS</wicri:regionArea><wicri:noRegion>WC2R 2LS</wicri:noRegion></affiliation><affiliation wicri:level="4"><country xml:lang="fr">France</country><wicri:regionArea>LIR — ABISS, Université de Rouen, 76821 Mont Saint Aignan Cedex</wicri:regionArea><orgName type="university">Université de Rouen</orgName><placeName><settlement type="city">Rouen</settlement><region type="region" nuts="2">Région Normandie</region><region type="old region" nuts="2">Haute-Normandie</region></placeName></affiliation><affiliation></affiliation><affiliation wicri:level="1"><country wicri:rule="url">France</country></affiliation></author></analytic><monogr></monogr><series><title level="j">Theoretical Computer Science</title><title level="j" type="abbrev">TCS</title><idno type="ISSN">0304-3975</idno><imprint><publisher>ELSEVIER</publisher><date type="published" when="1999">1999</date><biblScope unit="volume">218</biblScope><biblScope unit="issue">1</biblScope><biblScope unit="page" from="205">205</biblScope><biblScope unit="page" to="216">216</biblScope></imprint><idno type="ISSN">0304-3975</idno></series></biblStruct></sourceDesc><seriesStmt><idno type="ISSN">0304-3975</idno></seriesStmt></fileDesc><profileDesc><textClass><keywords scheme="KwdEn" xml:lang="en"><term>Abaaba</term><term>Algorithm</term><term>Appropriate factor</term><term>Computer science</term><term>Concatenation</term><term>Easy seed</term><term>Easy seeds</term><term>Ehrenfeucht algorithm</term><term>Elsevier science</term><term>Failure function</term><term>Formal language</term><term>Formal language theory</term><term>Hard seed</term><term>Hard seeds</term><term>Iliopoulos</term><term>Language theory</term><term>Lecture notes</term><term>Local period</term><term>Longest span</term><term>Main steps</term><term>Maximal quasiperiodic factors</term><term>Mouchardl</term><term>Optimal algorithm</term><term>Parallel string</term><term>Periodic words</term><term>Periodicity</term><term>Proper factor</term><term>Quasi periodic variation</term><term>Quasiperiodic</term><term>Quasiperiodic factor</term><term>Quasiperiodicity</term><term>Quasiperiodicity problem</term><term>Regularity</term><term>Right extension</term><term>String matching</term><term>Superposition</term><term>Wide area</term></keywords><keywords scheme="Pascal" xml:lang="fr"><term>Appariement chaîne</term><term>Langage formel</term><term>Régularité</term><term>Théorie langage</term><term>Variation quasi périodique</term></keywords><keywords scheme="Teeft" xml:lang="en"><term>Abaaba</term><term>Algorithm</term><term>Appropriate factor</term><term>Computer science</term><term>Concatenation</term><term>Easy seed</term><term>Easy seeds</term><term>Ehrenfeucht algorithm</term><term>Elsevier science</term><term>Failure function</term><term>Formal language theory</term><term>Hard seed</term><term>Hard seeds</term><term>Iliopoulos</term><term>Lecture notes</term><term>Local period</term><term>Longest span</term><term>Main steps</term><term>Maximal quasiperiodic factors</term><term>Mouchardl</term><term>Optimal algorithm</term><term>Parallel string</term><term>Periodic words</term><term>Periodicity</term><term>Proper factor</term><term>Quasiperiodic</term><term>Quasiperiodic factor</term><term>Quasiperiodicity</term><term>Quasiperiodicity problem</term><term>Regularity</term><term>Right extension</term><term>Superposition</term><term>Wide area</term></keywords></textClass><langUsage><language ident="en">en</language></langUsage></profileDesc></teiHeader><front><div type="abstract" xml:lang="en">Abstract: In this paper, we study word regularities and in particular extensions of the notion of the word period: quasiperiodicity, covers and seeds. We present overviews of algorithms for computing the quasiperiodicity, the covers and the seeds of a given word. We also present an overview of an algorithm that finds maximal word factors with the above regularities. Finally, we show how Fine and Wilf's Theorem fails if we try to extend it directly to quasiperiodicity, as well as a new property on concatenation of periodic words.</div></front></TEI><affiliations><list><country><li>Australie</li><li>France</li><li>Royaume-Uni</li></country><region><li>Haute-Normandie</li><li>Région Normandie</li></region><settlement><li>Rouen</li></settlement><orgName><li>Université de Rouen</li></orgName></list><tree><country name="Royaume-Uni"><noRegion><name sortKey="Iliopoulos, Costas S" sort="Iliopoulos, Costas S" uniqKey="Iliopoulos C" first="Costas S." last="Iliopoulos">Costas S. Iliopoulos</name></noRegion><name sortKey="Mouchard, Laurent" sort="Mouchard, Laurent" uniqKey="Mouchard L" first="Laurent" last="Mouchard">Laurent Mouchard</name></country><country name="Australie"><noRegion><name sortKey="Iliopoulos, Costas S" sort="Iliopoulos, Costas S" uniqKey="Iliopoulos C" first="Costas S." last="Iliopoulos">Costas S. Iliopoulos</name></noRegion></country><country name="France"><region name="Région Normandie"><name sortKey="Mouchard, Laurent" sort="Mouchard, Laurent" uniqKey="Mouchard L" first="Laurent" last="Mouchard">Laurent Mouchard</name></region><name sortKey="Mouchard, Laurent" sort="Mouchard, Laurent" uniqKey="Mouchard L" first="Laurent" last="Mouchard">Laurent Mouchard</name></country></tree></affiliations></record>Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Wicri/Asie/explor/AustralieFrV1/Data/Main/Exploration
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 00C423 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Main/Exploration/biblio.hfd -nk 00C423 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien
|wiki= Wicri/Asie
|area= AustralieFrV1
|flux= Main
|étape= Exploration
|type= RBID
|clé= ISTEX:10737BF78BD626F99E6C0CB224A3C20D46D86E87
|texte= Quasiperiodicity and string covering
}}
| This area was generated with Dilib version V0.6.33. |  |